Codeforces Round #107 (Div. 2)

A

弱智题，直接对着模拟即可。

Code

#include <cstdio>

int n, k, l, c, d, p, nl, np;

int min(int x, int y, int z) {
    if (x <= y && x <= z) return x;
    if (y <= x && y <= z) return y;
    if (z <= x && z <= y) return z;
}

int main() {
    scanf("%d%d%d%d%d%d%d%d", &n, &k, &l, &c, &d, &p, &nl, &np);
    printf("%d\n", min(k * l / (n * nl), p / (n * np),  c * d / n));
}
 

B

字符串模拟，记录一下每个人的名字和三种电话的个数即可。

Code

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

const int N = 105;

struct Friend {
    int sum, cnt[4];
    string name, num[N];
} a[N];

inline int check(string s) {
    int a1 = s[0] - '0';
    int a2 = s[1] - '0';
    int b1 = s[3] - '0';
    int b2 = s[4] - '0';
    int c1 = s[6] - '0';
    int c2 = s[7] - '0';
    if (a1 == a2 && a2 == b1 && b1 == b2 && b2 == c1 && c1 == c2) return 1;
    else if (a1 > a2 && a2 > b1 && b1 > b2 && b2 > c1 && c1 > c2) return 2;
    else return 3;
}

int n, t, p, g, ft, fp, fg;

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].sum >> a[i].name;
        for (int j = 1; j <= a[i].sum; j++) {
            cin >> a[i].num[j];
            a[i].cnt[check(a[i].num[j])]++;
        }
    }
    for (int i = 1; i <= n; i++) {
        t = max(t, a[i].cnt[1]);
        p = max(p, a[i].cnt[2]);
        g = max(g, a[i].cnt[3]);
    }
    cout << "If you want to call a taxi, you should call: ";
    for (int i = 1; i <= n; i++) {
        if (!ft && a[i].cnt[1] == t) ft = 1, cout << a[i].name;
        else if (a[i].cnt[1] == t) cout << ", " << a[i].name;
    }
    cout << ".\nIf you want to order a pizza, you should call: ";
    for (int i = 1; i <= n; i++) {
        if (!fp && a[i].cnt[2] == p) fp = 1, cout << a[i].name;
        else if (a[i].cnt[2] == p) cout << ", " << a[i].name;
    }
    cout << ".\nIf you want to go to a cafe with a wonderful girl, you should call: ";
    for (int i = 1; i <= n; i++) {
        if (!fg && a[i].cnt[3] == g) fg = 1, cout << a[i].name;
        else if (a[i].cnt[3] == g) cout << ", " << a[i].name;
    }
    cout << "." << endl;
}

C

比较简单的博弈。

注意到若 $q$ 为质数则先手必胜，若 $q$ 能拆为两个质数的乘积则后手必胜。

若 $q$ 含有三个及以上的质因子，则先手玩家可以一步把 $q$ 变为只由两个质数相乘的情况，故先手必胜。

只需要对 $q$ 分解质因数即可，时间复杂度 $O(\sqrt{q})$ 。

Code

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

long long x, k, ans;

int check(long long x)
{
    long long y = x, res = 1;
    for (long long i = 2; i * i <= x; i++)
    {
        while (x % i == 0 && i * i <= x)
        {
            k++;
            res *= i;
            x /= i;
            if (k == 2 && x != y)
            {
                k++;
                return res;
            }
        }
    }
    if (x != y) k++;
    return res;
}

int main()
{
    cin >> x;
    ans = check(x);
    if (k == 2) cout << "2" << endl;
    else
    {
        cout << "1" << endl;
        if (ans == 1) cout << "0";
        else cout << ans;
    }
    return 0;
}

D

考虑使用并查集，将区间 $[i,\,i+k-1]$ 对应的回文串每一对相同字符所在集合合并，最后查询不同集合个数 $c$ ，答案即为 $m^c$ 。

时间复杂度 $O(nk)$ 。

Code

#include <cstdio>

const int N = 2005;
const int mod = 1e9 + 7;

int fa[N], n, m, k;

int getf(int x) {
    return x == fa[x] ? x : fa[x] = getf(fa[x]);
}

void merge(int x, int y) {
    x = getf(x), y = getf(y);
    if (x != y) fa[y] = x;
}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 1; i + k - 1 <= n; i++) {
        for (int l = i, r = i + k - 1; l <= r; l++, r--)
            merge(l, r);
    }
    int res = 1;
    for (int i = 1; i <= n; i++) {
        if (getf(i) == i) 
            res = 1LL * res * m % mod;
    }
    printf("%d\n", res);
}

E

待补。